On the homotopy type of multipath complexes

A multipath in a directed graph is a disjoint union of paths. The multipath complex of a directed graph G is the simplicial complex whose faces are the multipaths of G. We compute Euler characteristics, and associated generating functions, of the multipath complexes of directed graphs from certain families, including transitive tournaments and complete bipartite graphs. We show that if G is a linear graph, polygon, small grid or transitive tournament, then the homotopy type of the multipath complex of G is always contractible or a wedge of spheres. We introduce a new technique for decomposing directed graphs into dynamical regions, which allows us to simplify the homotopy computations.